{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Binary Tree Tilt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findTilt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树的坡度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二叉树的根节点 <code>root</code> ，计算并返回 <strong>整个树 </strong>的坡度 。</p>\n",
    "\n",
    "<p>一个树的<strong> 节点的坡度 </strong>定义即为，该节点左子树的节点之和和右子树节点之和的 <strong>差的绝对值 </strong>。如果没有左子树的话，左子树的节点之和为 0 ；没有右子树的话也是一样。空结点的坡度是 0 。</p>\n",
    "\n",
    "<p><strong>整个树</strong> 的坡度就是其所有节点的坡度之和。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/10/20/tilt1.jpg\" style=\"width: 712px; height: 182px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,3]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>\n",
    "节点 2 的坡度：|0-0| = 0（没有子节点）\n",
    "节点 3 的坡度：|0-0| = 0（没有子节点）\n",
    "节点 1 的坡度：|2-3| = 1（左子树就是左子节点，所以和是 2 ；右子树就是右子节点，所以和是 3 ）\n",
    "坡度总和：0 + 0 + 1 = 1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/10/20/tilt2.jpg\" style=\"width: 800px; height: 203px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [4,2,9,3,5,null,7]\n",
    "<strong>输出：</strong>15\n",
    "<strong>解释：</strong>\n",
    "节点 3 的坡度：|0-0| = 0（没有子节点）\n",
    "节点 5 的坡度：|0-0| = 0（没有子节点）\n",
    "节点 7 的坡度：|0-0| = 0（没有子节点）\n",
    "节点 2 的坡度：|3-5| = 2（左子树就是左子节点，所以和是 3 ；右子树就是右子节点，所以和是 5 ）\n",
    "节点 9 的坡度：|0-7| = 7（没有左子树，所以和是 0 ；右子树正好是右子节点，所以和是 7 ）\n",
    "节点 4 的坡度：|(3+5+2)-(9+7)| = |10-16| = 6（左子树值为 3、5 和 2 ，和是 10 ；右子树值为 9 和 7 ，和是 16 ）\n",
    "坡度总和：0 + 0 + 0 + 2 + 7 + 6 = 15\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/10/20/tilt3.jpg\" style=\"width: 800px; height: 293px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [21,7,14,1,1,2,2,3,3]\n",
    "<strong>输出：</strong>9\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点数目的范围在 <code>[0, 10<sup>4</sup>]</code> 内</li>\n",
    "\t<li><code>-1000 &lt;= Node.val &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [binary-tree-tilt](https://leetcode.cn/problems/binary-tree-tilt/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [binary-tree-tilt](https://leetcode.cn/problems/binary-tree-tilt/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3]', '[4,2,9,3,5,null,7]', '[21,7,14,1,1,2,2,3,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        self.re = 0\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            leftsum = dfs(node.left)\n",
    "            rightsum = dfs(node.right)\n",
    "            self.re += abs(leftsum - rightsum)\n",
    "            return leftsum + rightsum + node.val\n",
    "\n",
    "        dfs(root)\n",
    "        return self.re\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        sum = 0\n",
    "\n",
    "        def dps(root):\n",
    "            nonlocal sum\n",
    "            if not root:\n",
    "                return 0\n",
    "            sum_left = dps(root.left)\n",
    "            sum_right = dps(root.right)\n",
    "            sum += abs(sum_left-sum_right)\n",
    "            return sum_left+sum_right+root.val\n",
    "        \n",
    "        dps(root)\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        def sumNodes(r):\n",
    "            if not r:\n",
    "                return 0\n",
    "            left = sumNodes(r.left)\n",
    "            right = sumNodes(r.right)\n",
    "            return r.val + left + right\n",
    "\n",
    "        def getAns(r):\n",
    "            nonlocal ans\n",
    "            if not r:\n",
    "                return 0\n",
    "            ans += abs(sumNodes(r.left) - sumNodes(r.right))\n",
    "            getAns(r.left)\n",
    "            getAns(r.right)\n",
    "            return ans\n",
    "\n",
    "        ans = 0\n",
    "        getAns(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: TreeNode) -> int:\n",
    "        slope=0\n",
    "        def dfs(root):\n",
    "            nonlocal slope\n",
    "            if not root:\n",
    "                return 0\n",
    "            left=dfs(root.left)\n",
    "            right=dfs(root.right)\n",
    "            slope+=abs(left-right)\n",
    "            return left+right+root.val\n",
    "        dfs(root)\n",
    "        return slope\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        def dfs(r):\n",
    "            nonlocal ans\n",
    "            if r is None:\n",
    "                return\n",
    "            t = 0\n",
    "            if r.left != None:\n",
    "                dfs(r.left)\n",
    "                r.val += r.left.val\n",
    "                t = r.left.val\n",
    "            if r.right != None:\n",
    "                dfs(r.right)\n",
    "                r.val += r.right.val\n",
    "                t = abs(t - r.right.val)\n",
    "            ans += abs(t)\n",
    "            \n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root: return 0\n",
    "        res=0\n",
    "        def dfs(root):\n",
    "            if not root: return 0\n",
    "            left=dfs(root.left)\n",
    "            right=dfs(root.right)\n",
    "            nonlocal res\n",
    "            res+=abs(left-right)\n",
    "            return left+right+root.val\n",
    "        dfs(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        self.res = 0\n",
    "        # dfs\n",
    "        def dfs(node) -> int:\n",
    "            if not node: return 0\n",
    "            left = dfs(node.left)\n",
    "            right = dfs(node.right)\n",
    "            cur = abs(left-right)\n",
    "            self.res += cur\n",
    "            return left + right + node.val\n",
    "        dfs(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = 0\n",
    "    \n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        self.dfs(root)\n",
    "        return self.ans\n",
    "\n",
    "    def dfs(self, node):\n",
    "        if node == None:\n",
    "            return 0\n",
    "        \n",
    "        sum_left = self.dfs(node.left)\n",
    "        sum_right = self.dfs(node.right)\n",
    "        self.ans += abs(sum_left - sum_right)\n",
    "        return sum_left + sum_right + node.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = 0\n",
    "\n",
    "    def findTilt(self, root: TreeNode) -> int:\n",
    "        self.dfs(root)\n",
    "        return self.ans\n",
    "\n",
    "    def dfs(self, node):\n",
    "        if not node:\n",
    "            return 0\n",
    "        sum_left = self.dfs(node.left)\n",
    "        sum_right = self.dfs(node.right)\n",
    "        self.ans += abs(sum_left - sum_right)\n",
    "        return sum_left + sum_right + node.val\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = 0\n",
    "    def findSum(self, root:Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        else:\n",
    "            sum_left = self.findSum(root.left)\n",
    "            sum_right = self.findSum(root.right)\n",
    "            self.ans += abs(sum_left - sum_right)\n",
    "            return sum_left + sum_right + root.val\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        self.findSum(root)\n",
    "        return self.ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTilt(self, root: TreeNode) -> int:\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0, 0\n",
    "            l_sum, l_diff = dfs(node.left)\n",
    "            r_sum, r_diff = dfs(node.right)\n",
    "            return l_sum + r_sum + node.val, l_diff + r_diff + abs(r_sum - l_sum)\n",
    "        return dfs(root)[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def nodesum(self, node):\n",
    "        sum = node.val\n",
    "        if node.left:\n",
    "            sum += self.nodesum(node.left)\n",
    "        if node.right:\n",
    "            sum += self.nodesum(node.right)\n",
    "        node.val = sum\n",
    "        return sum\n",
    "    \n",
    "    def nodetilt(self, node):\n",
    "        lefttilt = node.left.val if node.left else 0\n",
    "        righttilt = node.right.val if node.right else 0\n",
    "        tilt = abs(lefttilt - righttilt)\n",
    "        if node.left:\n",
    "            tilt += self.nodetilt(node.left)\n",
    "        if node.right:\n",
    "            tilt += self.nodetilt(node.right)\n",
    "        return tilt\n",
    "\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        self.nodesum(root)\n",
    "        return self.nodetilt(root)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        res = []\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            if not node.left and not node.right:\n",
    "                return node.val\n",
    "            leftsum = dfs(node.left)\n",
    "            rightsum = dfs(node.right)\n",
    "            res.append(abs(leftsum-rightsum))\n",
    "            return leftsum + rightsum + node.val\n",
    "        dfs(root)\n",
    "        return sum(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSum(self, root:Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        else:\n",
    "            return self.findSum(root.left) + self.findSum(root.right) + root.val\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        return self.findTilt(root.left) + self.findTilt(root.right) + abs(self.findSum(root.left) - self.findSum(root.right))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = 0\n",
    "\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        self.find(root)\n",
    "        return self.ans\n",
    "    \n",
    "    def find(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        x = self.find(root.left)\n",
    "        y = self.find(root.right)\n",
    "        self.ans += abs(x-y)\n",
    "        return x + y + root.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTilt(self, root):\n",
    "        result = self.dfs(root)\n",
    "        return result[1] + result[2]\n",
    "\n",
    "    def dfs(self, pitch):\n",
    "        if not pitch:\n",
    "            return 0, 0, 0\n",
    "        # 子树的和、子树的坡度、当前的坡度总和。\n",
    "        price1, tilt1, figure1 = self.dfs(pitch.left)\n",
    "        price2, tilt2, figure2 = self.dfs(pitch.right)\n",
    "        # 当前的坡度。\n",
    "        titlnow = abs(price2 - price1)\n",
    "        # 子树的坡度之和。\n",
    "        figurenow = tilt1 + tilt2 + figure1 + figure2\n",
    "        return price1 + price2 + pitch.val, titlnow, figurenow"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = 0\n",
    "\n",
    "    def findTilt(self, root: TreeNode) -> int:\n",
    "        self.dfs(root)\n",
    "        return self.ans\n",
    "\n",
    "    def dfs(self, node):\n",
    "        if not node:\n",
    "            return 0\n",
    "        sum_left = self.dfs(node.left)\n",
    "        sum_right = self.dfs(node.right)\n",
    "        self.ans += abs(sum_left - sum_right)\n",
    "        return sum_left + sum_right + node.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = 0\n",
    "\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        self.find(root)\n",
    "        return self.ans\n",
    "    \n",
    "    def find(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        x = self.find(root.left)\n",
    "        y = self.find(root.right)\n",
    "        self.ans += abs(x-y)\n",
    "        return x + y + root.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def node_sum(self, root: Optional[TreeNode]) -> int:\n",
    "        \"\"\"\n",
    "        节点之和\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return 0\n",
    "        \n",
    "        left = self.node_sum(root.left)\n",
    "        right = self.node_sum(root.right)\n",
    "\n",
    "        return root.val + left + right\n",
    "\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        left = self.findTilt(root.left)\n",
    "        right = self.findTilt(root.right)\n",
    "        root_tilt = abs(self.node_sum(root.left) - self.node_sum(root.right))\n",
    "\n",
    "        return root_tilt + left + right\n",
    "    \n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        self.ans = 0\n",
    "        def myfun(root):\n",
    "            if root == None:\n",
    "                return 0\n",
    "            if root.left == None and root.right == None:\n",
    "                return root.val\n",
    "\n",
    "            if root.left:\n",
    "                l = myfun(root.left)\n",
    "            else:\n",
    "                l = 0\n",
    "\n",
    "            if root.right:\n",
    "                r = myfun(root.right)\n",
    "            else:\n",
    "                r = 0\n",
    "            \n",
    "            self.ans += abs(l - r)\n",
    "\n",
    "            return l + r + root.val\n",
    "        myfun(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        def Sum(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            return root.val + Sum(root.left) + Sum(root.right)\n",
    "        def f(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            return abs(Sum(root.left) - Sum(root.right)) + f(root.left) + f(root.right)\n",
    "        return f(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        self.ans = 0\n",
    "        def f(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            if node.left:\n",
    "                \n",
    "                node.left.val += f(node.left)\n",
    "                L = node.left.val\n",
    "            else:\n",
    "                L = 0\n",
    "            if node.right:\n",
    "                \n",
    "                node.right.val += f(node.right)\n",
    "                R = node.right.val\n",
    "            else:\n",
    "                R = 0\n",
    "            self.ans += abs(L-R)\n",
    "            return L + R\n",
    "        f(root)\n",
    "        return self.ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "      def dfs(root):\n",
    "        if root:\n",
    "          tot1, diff1= dfs(root.left)\n",
    "          tot2,diff2= dfs(root.right)\n",
    "          return tot1+tot2+root.val,diff1+diff2+abs(tot1-tot2)\n",
    "        else:\n",
    "          return 0,0\n",
    "      return dfs(root)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            sum_left=dfs(root.left)\n",
    "            sum_right=dfs(root.right)\n",
    "            ans=abs(sum_left-sum_right)\n",
    "            res.append(ans)\n",
    "            return sum_left+sum_right+root.val\n",
    "\n",
    "        res=[]\n",
    "        dfs(root)\n",
    "        return sum(res)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        self.res = 0\n",
    "        self.sumTreeVal(root)\n",
    "        return self.res\n",
    "\n",
    "    def sumTreeVal(self, node: TreeNode):\n",
    "        if node is None:\n",
    "            return 0\n",
    "        left = self.sumTreeVal(node.left)\n",
    "        right = self.sumTreeVal(node.right)\n",
    "        self.res += abs(left - right)\n",
    "        return left + right + node.val\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        def recur(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            lv=recur(root.left)\n",
    "            rv=recur(root.right)\n",
    "            self.result+=abs(lv-rv)\n",
    "            return lv+rv+root.val\n",
    "        \n",
    "        self.result=0\n",
    "        recur(root)\n",
    "\n",
    "        return self.result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        left_sum = self.traversal(root.left)\n",
    "        right_sum = self.traversal(root.right)\n",
    "        return abs(left_sum-right_sum)+self.findTilt(root.left)+self.findTilt(root.right)\n",
    "    \n",
    "    def traversal(self, node):\n",
    "        if node is None:\n",
    "            return 0\n",
    "        return node.val+self.traversal(node.left)+self.traversal(node.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        self.res = 0\n",
    "        def Slope(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            else:\n",
    "                L = Slope(root.left)\n",
    "                R = Slope(root.right)\n",
    "                self.res += abs(L - R)\n",
    "                return L + R + root.val\n",
    "        Slope(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = 0\n",
    "\n",
    "    def findTilt(self, root: TreeNode) -> int:\n",
    "        self.dfs(root)\n",
    "        return self.ans\n",
    "\n",
    "    def dfs(self, node):\n",
    "        if not node:\n",
    "            return 0\n",
    "        sum_left = self.dfs(node.left)\n",
    "        sum_right = self.dfs(node.right)\n",
    "        self.ans += abs(sum_left - sum_right)\n",
    "        return sum_left + sum_right + node.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 0\n",
    "        def getRes(root):\n",
    "            nonlocal res\n",
    "            if root == None:\n",
    "                return 0\n",
    "            l = getRes(root.left)\n",
    "            r = getRes(root.right)\n",
    "            res = res + abs(l-r)\n",
    "            return root.val + l + r\n",
    "        getRes(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = 0\n",
    "    \n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        self.dfs(root)\n",
    "        return self.ans\n",
    "\n",
    "    def dfs(self,node):\n",
    "        if not node:\n",
    "            return 0\n",
    "        sum_left = self.dfs(node.left)\n",
    "        sum_right = self.dfs(node.right)\n",
    "        self.ans += abs(sum_left-sum_right)\n",
    "        return sum_left + sum_right + node.val\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        def sumNodes(r):\n",
    "            if not r:\n",
    "                return 0\n",
    "            self.s += r.val\n",
    "            sumNodes(r.left)\n",
    "            sumNodes(r.right)\n",
    "            return self.s\n",
    "\n",
    "        def getAns(r):\n",
    "            nonlocal ans\n",
    "            if not r:\n",
    "                return 0\n",
    "            self.s = 0\n",
    "            a = sumNodes(r.left)\n",
    "            self.s = 0\n",
    "            b = sumNodes(r.right)\n",
    "            c = abs(a - b)\n",
    "            ans += c\n",
    "            getAns(r.left)\n",
    "            getAns(r.right)\n",
    "            return ans\n",
    "\n",
    "        ans = 0\n",
    "        d = getAns(root)\n",
    "        return d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        elif not root.left and not root.right:\n",
    "            return 0\n",
    "        elif bool(root.left)+bool(root.right) == 1:\n",
    "            if root.left:\n",
    "                return abs(self.sumTree(root.left)) + self.findTilt(root.left)\n",
    "            if root.right:\n",
    "                return abs(self.sumTree(root.right)) + self.findTilt(root.right)\n",
    "        return abs(self.sumTree(root.left)-self.sumTree(root.right)) + self.findTilt(root.left) + self.findTilt(root.right)\n",
    "    \n",
    "\n",
    "    def sumTree(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        elif not root.left and not root.right:\n",
    "            return root.val\n",
    "        else:\n",
    "            return self.sumTree(root.left) + self.sumTree(root.right) + root.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    ans = 0\n",
    "    def find(self, root: Optional[TreeNode]) -> int:\n",
    "        if (root is None):\n",
    "            return 0\n",
    "        l = self.find(root.left)\n",
    "        r = self.find(root.right)\n",
    "        tmp = root.val + l + r\n",
    "        root.val = abs(r - l)\n",
    "        self.ans += root.val\n",
    "        # print(l, r, root.val)\n",
    "        return tmp\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        if (root is None):\n",
    "            return 0\n",
    "        self.find(root)\n",
    "        # 计算坡度总和\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        def subtreeSumAndTilt(node):\n",
    "            if not node:\n",
    "                return 0, 0\n",
    "            left_sum, left_tilt = subtreeSumAndTilt(node.left)\n",
    "            right_sum, right_tilt = subtreeSumAndTilt(node.right)\n",
    "            # 递归每个节点的左右二叉树\n",
    "\n",
    "            node_tilt = abs(left_sum - right_sum)\n",
    "            total_tilt = left_tilt + right_tilt + node_tilt\n",
    "            # 根据递归中返回的值进行计算坡度\n",
    "\n",
    "            return left_sum + right_sum + node.val, total_tilt\n",
    "\n",
    "        # 递归返回每个节点的值供上一个调用者的变量赋值,\n",
    "\n",
    "        _, result = subtreeSumAndTilt(root)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        result = 0\n",
    "        def dfs(node):\n",
    "            if node:\n",
    "                left, right = dfs(node.left), dfs(node.right)\n",
    "                nonlocal result\n",
    "                result += abs(left - right)\n",
    "                return node.val + left + right\n",
    "            return 0\n",
    "        dfs(root)\n",
    "        return result\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        def get_subtree_value(node:TreeNode):\n",
    "            if node is None:\n",
    "                return 0\n",
    "            nonlocal ans\n",
    "            left = get_subtree_value(node.left)\n",
    "            right = get_subtree_value(node.right)\n",
    "            ans += abs(left-right)\n",
    "            return left+right+node.val\n",
    "        ans = 0\n",
    "        get_subtree_value(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    ans = 0\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        self.ans = 0\n",
    "        def cal(root):\n",
    "            if not root: return 0\n",
    "            left_nodes = cal(root.left)\n",
    "            right_nodes = cal(root.right)\n",
    "            self.ans += abs(left_nodes-right_nodes)\n",
    "\n",
    "            return left_nodes+right_nodes+root.val\n",
    "        \n",
    "        cal(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.sum_notes = dict()\n",
    "\n",
    "    def node_sum(self, root: Optional[TreeNode]) -> int:\n",
    "        \"\"\"\n",
    "        节点之和\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return 0\n",
    "        \n",
    "        if root not in self.sum_notes:\n",
    "            left = self.node_sum(root.left)\n",
    "            right = self.node_sum(root.right)\n",
    "            self.sum_notes[root] = root.val + left + right\n",
    "\n",
    "        return self.sum_notes[root]\n",
    "\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        left = self.findTilt(root.left)\n",
    "        right = self.findTilt(root.right)\n",
    "        root_tilt = abs(self.node_sum(root.left) - self.node_sum(root.right))\n",
    "\n",
    "        return root_tilt + left + right\n",
    "    \n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        return self.helper(root)[1]\n",
    "    def helper(self, root):\n",
    "        if not root:\n",
    "            return 0, 0\n",
    "        sum_l, tilt_l = self.helper(root.left)\n",
    "        sum_r, tilt_r = self.helper(root.right)\n",
    "        return sum_l + sum_r + root.val, tilt_l + tilt_r + abs(sum_l - sum_r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        res = []\n",
    "\n",
    "        def deepin(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            if not node.left and not node.right:\n",
    "                return node.val\n",
    "            leftsum = deepin(node.left)\n",
    "            rightsum = deepin(node.right)\n",
    "            res.append(abs(leftsum - rightsum))\n",
    "            return leftsum + rightsum + node.val\n",
    "\n",
    "        deepin(root)\n",
    "\n",
    "        return sum(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = 0\n",
    "\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        self.find(root)\n",
    "        return self.ans\n",
    "    \n",
    "    def find(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        x = self.find(root.left)\n",
    "        y = self.find(root.right)\n",
    "        self.ans += abs(x-y)\n",
    "        return x + y + root.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: TreeNode) -> int:\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0, 0\n",
    "            l_sum, l_diff = dfs(node.left)\n",
    "            r_sum, r_diff = dfs(node.right)\n",
    "            return l_sum + r_sum + node.val, l_diff + r_diff + abs(r_sum - l_sum)\n",
    "        return dfs(root)[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = 0\n",
    "\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        self.find(root)\n",
    "        return self.ans\n",
    "    \n",
    "    def find(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        x = self.find(root.left)\n",
    "        y = self.find(root.right)\n",
    "        self.ans += abs(x-y)\n",
    "        return x + y + root.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        self.ans = 0\n",
    "        def dfs(root):\n",
    "            if not root:return 0\n",
    "            l = dfs(root.left)\n",
    "            r = dfs(root.right)\n",
    "            self.ans += abs(l - r)\n",
    "            return l + r + root.val\n",
    "        dfs(root)\n",
    "        return self.ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\r\n",
    "        ret=0\r\n",
    "        def traverse(root:TreeNode):\r\n",
    "            nonlocal ret\r\n",
    "            if not root:\r\n",
    "                return 0\r\n",
    "            sum_left=traverse(root.left)\r\n",
    "            sum_right=traverse(root.right)\r\n",
    "            ret+=abs(sum_left-sum_right)\r\n",
    "            return sum_left+sum_right+root.val\r\n",
    "        traverse(root)\r\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        self.res = 0\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            left_sum = dfs(node.left)\n",
    "            right_sum = dfs(node.right)\n",
    "            self.res += abs(left_sum - right_sum)\n",
    "            return left_sum + right_sum + node.val\n",
    "        dfs(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        def total_val(r):\n",
    "            if not r: return 0\n",
    "            left = total_val(r.left)\n",
    "            right = total_val(r.right)\n",
    "            return r.val+left+right\n",
    "        self.tilt = 0\n",
    "\n",
    "        def dfs(r):\n",
    "            if not r:return 0\n",
    "            dfs(r.left)\n",
    "            dfs(r.right)\n",
    "            self.tilt += abs(total_val(r.left)-total_val(r.right))\n",
    "            return self.tilt\n",
    "        return dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root):\n",
    "        self.ans = 0\n",
    "        self.travelsal(root)\n",
    "        return self.ans\n",
    "\n",
    "    def travelsal(self, node):\n",
    "        if not node:\n",
    "            return 0\n",
    "\n",
    "        sum_left = self.travelsal(node.left)\n",
    "        sum_right = self.travelsal(node.right)\n",
    "\n",
    "        self.ans += abs(sum_right - sum_left)\n",
    "        return sum_left + sum_right + node.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:     \n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        res = []\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            sum_l = dfs(root.left)\n",
    "            sum_r = dfs(root.right)\n",
    "            res.append(abs(sum_l-sum_r))\n",
    "            return sum_l + sum_r + root.val\n",
    "        dfs(root)\n",
    "        return sum(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        self.res = 0\n",
    "        self.sum(root)\n",
    "        return self.res\n",
    "        \n",
    "    def sum(self, root):\n",
    "        if root is None: return 0\n",
    "        left = self.sum(root.left) if root.left is not None else 0\n",
    "        right = self.sum(root.right) if root.right is not None else 0\n",
    "        self.res += abs(left - right)\n",
    "        return left + right + root.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = 0\n",
    "\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        a = self.dfs(root)\n",
    "        print(a)\n",
    "        return self.ans\n",
    "    \n",
    "    def dfs(self, node):\n",
    "        if not node:\n",
    "            return 0\n",
    "        L = self.dfs(node.left)\n",
    "        R = self.dfs(node.right)\n",
    "        self.ans += abs(L-R)\n",
    "        return L + R + node.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = 0\n",
    "    \n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        self.dfs(root)\n",
    "        return self.ans\n",
    "    \n",
    "    def dfs(self,root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        suml = self.dfs(root.left)\n",
    "        sumr = self.dfs(root.right)\n",
    "        self.ans += abs(suml - sumr)\n",
    "        return suml + sumr + root.val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(cur):\n",
    "            if not cur:\n",
    "               return 0\n",
    "            if not cur.right and not cur.left:\n",
    "                return cur.val\n",
    "            left=dfs(cur.left)\n",
    "            right=dfs(cur.right)\n",
    "            res.append(abs(left-right))\n",
    "            return left+right+cur.val\n",
    "        res=[]\n",
    "        dfs(root)\n",
    "        return sum(res)    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    ans=0\n",
    "    def helper(self, root):\n",
    "        if root is None:\n",
    "            return 0\n",
    "        left=self.helper(root.left)\n",
    "        right=self.helper(root.right)\n",
    "        self.ans+=abs(left-right)\n",
    "        return left+right+root.val\n",
    "\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        self.ans=0\n",
    "        self.helper(root)\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        def dfs(node):\n",
    "            nonlocal ans\n",
    "            if not node:\n",
    "                return 0\n",
    "            l = dfs(node.left)\n",
    "            r = dfs(node.right)\n",
    "            ans += abs(l - r)\n",
    "            return l + r + node.val\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: TreeNode) -> int:\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0, 0\n",
    "            l_sum, l_diff = dfs(node.left)\n",
    "            r_sum, r_diff = dfs(node.right)\n",
    "            return l_sum + r_sum + node.val, l_diff + r_diff + abs(r_sum - l_sum)\n",
    "        return dfs(root)[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        self.ans=0\n",
    "        def dfs(root):\n",
    "            if not root: return 0\n",
    "            left=dfs(root.left)\n",
    "            right=dfs(root.right)\n",
    "            self.ans+=abs(left-right)\n",
    "            return left+right+root.val\n",
    "        dfs(root)\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        tilt, _, = self.subTreeSum(root)\n",
    "\n",
    "        return tilt \n",
    "\n",
    "    def subTreeSum(self, root):\n",
    "        if root is None:\n",
    "            return 0, 0\n",
    "\n",
    "        left_tilt, left_sum = self.subTreeSum(root.left)\n",
    "        right_tilt, right_sum = self.subTreeSum(root.right)\n",
    "\n",
    "        tree_sum = left_sum + right_sum + root.val \n",
    "\n",
    "        tilt = abs(left_sum - right_sum) + left_tilt + right_tilt\n",
    "\n",
    "        return tilt, tree_sum\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        def dfs(node):\n",
    "            nonlocal ans\n",
    "            if node is None:\n",
    "                return 0\n",
    "            left_sum = dfs(node.left)\n",
    "            right_sum = dfs(node.right)\n",
    "            ans += abs(left_sum - right_sum)\n",
    "            return left_sum + right_sum + node.val\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        elif not root.left and not root.right:\n",
    "            return 0\n",
    "        elif bool(root.left)+bool(root.right) == 1:\n",
    "            if root.left:\n",
    "                return abs(self.sumTree(root.left)) + self.findTilt(root.left)\n",
    "            if root.right:\n",
    "                return abs(self.sumTree(root.right)) + self.findTilt(root.right)\n",
    "        return abs(self.sumTree(root.left)-self.sumTree(root.right)) + self.findTilt(root.left) + self.findTilt(root.right)\n",
    "    \n",
    "\n",
    "    def sumTree(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        elif not root.left and not root.right:\n",
    "            return root.val\n",
    "        else:\n",
    "            return self.sumTree(root.left) + self.sumTree(root.right) + root.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        def dfs(root):\n",
    "            if root is None:\n",
    "                return 0\n",
    "            nonlocal ans\n",
    "            ls, rs = dfs(root.left), dfs(root.right)\n",
    "            ans += abs(ls-rs)\n",
    "            return ls + rs + root.val\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        ret=0\n",
    "        # return sum of subtree of this root \n",
    "        def dfs(root:Optional[TreeNode])->int:\n",
    "            if not root:\n",
    "                return 0\n",
    "            left_sum=dfs(root.left)\n",
    "            right_sum=dfs(root.right)\n",
    "            # add tile of this root\n",
    "            nonlocal ret\n",
    "            ret+=abs(left_sum-right_sum)\n",
    "            return left_sum+right_sum+root.val\n",
    "        dfs(root)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(node):\n",
    "            \n",
    "            if not node:\n",
    "                return 0,0\n",
    "            else:\n",
    "                sl,pl=dfs(node.left)\n",
    "                sr,pr=dfs(node.right)\n",
    "                return node.val+sl+sr,abs(sl-sr)+pl+pr\n",
    "        \n",
    "        a,b=dfs(root)\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = 0\n",
    "\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        self.dbs(root)\n",
    "        return self.ans\n",
    "\n",
    "    def dbs(self, root):\n",
    "        self.ans += abs(self.cal_summ(root.left) - self.cal_summ(root.right))\n",
    "        if root.left:\n",
    "            self.dbs(root.left)\n",
    "        if root.right:\n",
    "            self.dbs(root.right)\n",
    "\n",
    "    def cal_summ(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        elif not root.left and not root.right:\n",
    "            return root.val\n",
    "        else:\n",
    "            return root.val + self.cal_summ(root.left) + self.cal_summ(root.right)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        self.tilt = 0\n",
    "        self.dfs(root)\n",
    "        return self.tilt\n",
    "\n",
    "    def dfs(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        L = self.dfs(root.left)\n",
    "        R = self.dfs(root.right)\n",
    "        self.tilt += abs(L - R)\n",
    "        return L + R + root.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "      self.ans=0\n",
    "      def sumval(root):\n",
    "        if not root:\n",
    "          return 0\n",
    "        elif not root.left and not root.right:\n",
    "          return root.val\n",
    "        else:\n",
    "          L=sumval(root.left)\n",
    "          R=sumval(root.right)\n",
    "          self.ans=self.ans+abs(L-R)\n",
    "          return root.val+L+R\n",
    "      sumval(root)\n",
    "      return self.ans\n",
    "          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        self.res = 0\n",
    "        def dfs(root):\n",
    "            if not root: return 0\n",
    "            left, right = dfs(root.left), dfs(root.right)\n",
    "            self.res += abs(left - right)\n",
    "            return left + root.val + right\n",
    "        dfs(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\r\n",
    "        self.ans = 0\r\n",
    "        def dfs(node):\r\n",
    "            if not node:\r\n",
    "                return 0\r\n",
    "            sum_left = dfs(node.left)\r\n",
    "            sum_right = dfs(node.right)\r\n",
    "            self.ans += abs(sum_left - sum_right)\r\n",
    "            return sum_left + sum_right + node.val\r\n",
    "\r\n",
    "        dfs(root)\r\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        self.res = 0\n",
    "        def Slope(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            else:\n",
    "                L = Slope(root.left)\n",
    "                R = Slope(root.right)\n",
    "                self.res += abs(L - R)\n",
    "                return L + R + root.val\n",
    "        Slope(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: Optional[TreeNode]) -> int:\n",
    "        self.res = 0\n",
    "        self.help(root)\n",
    "        return self.res\n",
    "\n",
    "    def help(self, node):\n",
    "        # sum, po\n",
    "        if node is None:\n",
    "            return 0\n",
    "        l_sum= self.help(node.left)\n",
    "        r_sum= self.help(node.right)\n",
    "        cur_sum = l_sum + r_sum + node.val\n",
    "        self.res += abs(l_sum-r_sum)\n",
    "        return cur_sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTilt(self, root: TreeNode) -> int:\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0, 0\n",
    "            l_sum, l_diff = dfs(node.left)\n",
    "            r_sum, r_diff = dfs(node.right)\n",
    "            return l_sum + r_sum + node.val, l_diff + r_diff + abs(r_sum - l_sum)\n",
    "        return dfs(root)[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findTilt(self, root: TreeNode) -> int:\n",
    "        def dfs_sum(root):\n",
    "            if root:\n",
    "                return dfs_sum(root.left)+dfs_sum(root.right) + root.val\n",
    "            return 0\n",
    "\n",
    "        def tilt(root):\n",
    "            if root:\n",
    "                return abs(dfs_sum(root.right)-dfs_sum(root.left))\n",
    "            return 0\n",
    "\n",
    "        def dfs(root):\n",
    "            if root:\n",
    "                return dfs(root.right)+dfs(root.left) + tilt(root)\n",
    "            return 0\n",
    "\n",
    "        print(tilt(root))\n",
    "\n",
    "        return dfs(root)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
